package cn.fxzhang.leetcode.no00;

/**
 * 6. Z 字形变换
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 输出：PAHNAPLSIIGYIR
 * 1 <= s.length <= 1000
 * 1 <= numRows <= 1000
 *
 * 类型：字符串处理/指针
 * 题解：记录坐标和方向，到达最后一行/回到第一行时，调整方向
 * 时间复杂度：O(N)
 * 空间复杂度：O(N^Row)
 *
 * 提交记录(1/1)：
 * 执行用时: 22 ms, 击败了15.17%
 * 内存消耗: 40.7 MB, 击败了6.82%
 *
 * 【中等】通过次数236,260提交次数473,808
 * @author 张晓帆
 * @date 2021/4/6
 */
public class P0006_Zigzag_Conversion {

    public String convert(String s, int numRows) {
        if (numRows == 1){
            return s;
        }
        char[][] arr = new char[numRows][s.length()];
        arr[0][0] = s.charAt(0);
        int i = 1;
        int j = 0;
        int deltaI = 1;
        int deltaJ = 0;
        for (int k=1; k<s.length(); k++){
            arr[i][j] = s.charAt(k);
            if (deltaI == 1 && i+1 == numRows){
                deltaI = -1;
                deltaJ = 1;
            } else if (i == 0){
                deltaI = 1;
                deltaJ = 0;
            }
            i = i+deltaI;
            j = j+deltaJ;
        }
        StringBuilder res = new StringBuilder();
        for (int x=0; x<numRows; x++){
            for (int y=0; y<=j; y++){
                if (arr[x][y] != 0) {
                    res.append(arr[x][y]);
                }
            }
        }
        return res.toString();
    }
}
